

function Octree(x, y, z, radius, maxLeafNodeSize) {
    this.x = x;
    this.y = y;
    this.z = z;
    this.radius = radius;
    this.maxLeafNodeSize = maxLeafNodeSize;
    this.stars = [];
    this.children = null;
    this.maxLuminosity = 0;
}

Octree.prototype.whichChild = function(star) {
    var childNumber = 0;
    var p = star.location;
    if (p.x > this.x) childNumber += 4;
    if (p.y > this.y) childNumber += 2;
    if (p.z > this.z) childNumber += 1;
    return childNumber;
};

function getDirection(childNumber) {
    switch(childNumber) {
    case 0: return [-1, -1, -1];
    case 1: return [-1, -1, +1];
    case 2: return [-1, +1, -1];
    case 3: return [-1, +1, +1];
    case 4: return [+1, -1, -1];
    case 5: return [+1, -1, +1];
    case 6: return [+1, +1, -1];
    case 7: return [+1, +1, +1];
    };
    return null;
};

Octree.prototype.insert = function(star) {
    if (star.luminosity > this.maxLuminosity) {
        this.maxLuminosity = star.luminosity;
    }
    if (this.children == null) {
        this.stars.push(star);
	var numStars = this.stars.length;
        if (numStars > this.maxLeafNodeSize) {
            this.splitLeaf();
	}
    } else {
        childNumber = this.whichChild(star);
        child = this.children[childNumber];
        child.insert(star);
    }
};

Octree.prototype.totalNumStars = function() {
    if (this.children == null) {
        return this.stars.length;
    }
    var total = 0;
    var n = this.children.length;
    for (var i = 0; i < n; ++i) {
	var child = this.children[i];
        total += child.totalNumStars();
    }
    return total;
};

Octree.prototype.numNodes = function() {
    if (this.children == null) {
        return 1;
    }
    var total = 0;
    var n = this.children.length;
    for (var i = 0; i < n; ++i) {
	var child = this.children[i];
        total += child.numNodes();
    }
    return total + 1;
};

Octree.prototype.splitLeaf = function() {
    this.children = [];
    var r = 0.5 * this.radius;
    for (var i = 0; i < 8; ++i) {
	var direction = getDirection(i);
	var dx = direction[0];
	var dy = direction[1];
	var dz = direction[2];
	var x = this.x + dx * r;
	var y = this.y + dy * r;
	var z = this.z + dz * r;
	var child = new Octree(x, y, z, r, this.maxLeafNodeSize);
	this.children.push(child);
    };
    var n = this.stars.length;
    for (var i = 0; i < n; ++i) {
	var star = this.stars[i];
	this.insert(star);
    }
    this.stars = null;
};

Octree.prototype.isVisible = function(p, brightnessThreshold) {
    var dx = this.x - p.x;
    var dy = this.y - p.y;
    var dz = this.z - p.z;
    var r = this.radius;
    var squaredDistance = dx * dx + dy * dy + dz * dz - 3 * r * r;
    if (squaredDistance <= 0) {
	return true;
    } else {
	var brightness = this.maxLuminosity / squaredDistance;
	return brightness > brightnessThreshold;
    }
};

Octree.prototype.render = function(cameraPosition,
				   cameraDirection, upDirection, leftDirection,
				   width, height, context,
				   brightnessThreshold) {
    if (!this.isVisible(cameraPosition, brightnessThreshold)) {
	return 0;
    }
    if (this.children != null) {
	var numStars = 0;
	var n = this.children.length;
	for (var i = 0; i < n; ++i) {
	    var child = this.children[i];
	    numStars += child.render(cameraPosition, cameraDirection,
				     upDirection, leftDirection,
				     width, height, context,
				     brightnessThreshold);
	}
	return numStars;
    }
    if (this.stars != null) {
	var n = this.stars.length;
	for (var i = 0; i < n; ++i) {
	    var star = this.stars[i];
	    var translated = star.location.subtract(cameraPosition);
	    var rotated = translated.basisProjection(leftDirection,
						     upDirection,
						     cameraDirection);
	    star.render(rotated, width, height, context);
	}
	return n;
    }
};
